/*
https://leetcode.cn/problems/count-complete-tree-nodes/submissions/565530781/
2024/9/15
二分搜索
*/



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0; // 如果根节点为空，返回0，表示没有节点

        // 判断当前子树是否为满完全二叉树
        TreeNode *left = root->left, *right = root->right;
        int left_depth = 1, right_depth = 1;

        // 计算左子树的深度
        while (left) {
            left_depth++;
            left = left->left;
        }

        // 计算右子树的深度
        while (right) {
            right_depth++;
            right = right->right;
        }

        // 如果左子树和右子树的深度相同，说明当前子树是满完全二叉树
        if (left_depth == right_depth) {
            // 满完全二叉树的节点数可以通过公式计算：2^depth - 1
            return pow(2, left_depth) - 1;
        }

        // 如果不是满完全二叉树，按照普通的方法递归计算节点数
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};